Count

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

img

Sample Input

6 3

Sample Output

2248

HINT

img

Solution

这必然是一道数学题。首先，显然的有：如果 π xi <= n ^ 2m 时，显然是没有限制的。并且 n ^ m = sqrt(n ^ 2m)。

我们记录：s1 表示 < n ^ m 的个数，s2 表示 = n ^ m 的个数，s3 表示 > n ^ m 的个数。

那么显然有 s1 = s3。并且无限制方案数 = (n的约数个数)^2m，这时候，我们只要求出 s2 即可。

问题转化为：在 2m 个位置中 填入若干个数，记 n的某一质因子为 x，那我们要满足 填入数中 x 的指数之和 = m * （n 中这个 x 的指数）。

那么显然对于n的每一个质因子 DP 一下，f[i][j]表示填到了第 i 个数， 和为 j 的方案数。（由于 填数只能是 n 的约数，还要保证 每个数的 x 的指数 < n 中这个 x 的指数）。显然 统计的时候乘上 f[2 * m][指数 * m]。

最后算一下s1 + s2即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 200005;
const int MOD = 998244353;

int n, m;
int a[ONE], T;
int f[2][35 * 100], Ans = 1;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

int Quickpow(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (s64)res * a % MOD;
        a = (s64)a * a % MOD;
        b >>= 1;
    }
    return res;
}

void Deal(int Num)
{
    memset(f, 0, sizeof(f)); f[0][0] = 1;
    int A = 1, B = 0;

    for(int id = 1; id <= 2 * m; id++)
    {
        swap(A, B); memset(f[B], 0, sizeof(f[B]));
        for(int j = 0; j <= Num * m; j++)
            for(int k = 0; k <= Num && k <= j; k++)
                f[B][j] = (f[B][j] + f[A][j - k]) % MOD;
    }

    Ans = (s64)Ans * f[B][Num * m] % MOD;
}

void Factor(int x)
{
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0)
        {
            int Num = 0;
            while(x % i == 0) x /= i, Num++;
            Deal(Num);
        }

    if(x > 1) Deal(1);
}

int main()
{
    n = get();    m = get();
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0) {T++; if(n / i != i) T++;}

    Factor(n);

    printf("%d", ((s64)(Quickpow(T, 2*m) - Ans + MOD) % MOD * Quickpow(2, MOD - 2) % MOD + Ans) % MOD);
}